#include <iostream>
#include <vector>
using namespace std;

//class Solution {
//public:
//    vector<int> findDiagonalOrder(vector<vector<int>>& matrix) {
//        // 定义一个一维数组来接收二维数组指定顺序下标所对应的值
//        vector<int> ans;
//        if(matrix.empty()){
//            // 若传入的二维数组是一个空数组，则直接返回新数组
//            return ans;
//        }
//
//        // 获取二维数组的总行数与总列数(即下方代码的边界：最大行下标与最大列数下标)
//        int row = matrix.size();
//        int col = matrix[0].size();
//
//        // 定义两个新变量来标识要传入新数组的值的下标
//        int c = 0;
//        int r = 0;
//
//        // 行数+列数-1=遍历的总次数
//        for (int i = 0;i < row+col-1;i++){
//            // 如果为偶数次遍历(i = 1, i = 3)
//            if (i % 2){
//            // i = 1时进行第二次for遍历
//            // if (1 % 2)
//
//            // i = 3时进行第四次for遍历
//            // if (3 % 2)
//
//                // 限定最大值 若下标值超出了列界限，就赋值为列下标最大值(即col-1)
//                c = (i < col) ? i : col-1;
//                // 第二次for遍历
//                // c = (1 < 3) ? 1 : 2;
//
//                // 第四次for遍历
//                // c = (3 < 3) ? 3 : 2;
//
//                // 行下标r+列下标c=遍历次数i(注：i = 0时进行第一次遍历)，由此得出r = i - c;
//                r = i - c;
//                // 第二次for遍历
//                // r = 1 - 1;
//
//                // 第四次for遍历
//                // r = 2 - 1;
//
//                // 偶数次遍历列数自减1，行数自加1
//                // 限定列下标c自减到0(不为负数)且行下标r自增到总行数row(不超出界限)
//                while(c >= 0 && r < row) {
//                // 第二次for遍历下的第一次while循环
//                // while(1 >= 0 && 0 < 3)
//                // 第二次for遍历下的第二次while循环
//                // while(0 >= 0 && 1 < 3)
//
//                // 第四次for遍历下的第一次while循环
//                // while(2 >= 0 && 1 < 3)
//                // 第四次for遍历下的第二次while循环
//                // while(1 >= 0 && 2 < 3)
//
//                    // 每次赋值结束后行数+1，列数-1
//                    ans.push_back(matrix[r++][c--]);
//                    // 第二次for遍历下的第一次while循环
//                    // ans.push_back(matrix[0++][1--]);  // 2
//                    // 第二次for遍历下的第二次while循环
//                    // ans.push_back(matrix[1++][0--]);  // 4
//
//                    // 第四次for遍历下的第一次while循环
//                    // ans.push_back(matrix[1++][2--]);  // 6
//                    // 第四次for遍历下的第二次while循环
//                    // ans.push_back(matrix[2++][1--]);  // 8
//                }
//            // 如果为奇数次遍历(i = 0, i = 2, i = 4)
//            } else {
//            // i = 0时进行第一次for遍历
//            // else if (0 % 2)
//
//            // i = 2时进行第三次for遍历
//            // else if (2 % 2)
//
//            // i = 4时进行第五次for遍历
//            // else if (4 % 2)
//
//                // 限定最大值 若下标值超出了行界限，就赋值为行下标最大值(即row-1)
//                r = (i < row) ? i : row-1;
//                // 第一次for遍历
//                // r = (0 < 3) ? 0 : 2;
//
//                // 第三次for遍历
//                // r = (2 < 3) ? 2 : 2;
//
//                // 第五次for遍历
//                // r = (4 < 3) ? 4 : 2;
//
//                // 行下标r+列下标c=遍历次数i(注：i = 0时进行第一次遍历)，由此得出c = i - r;
//                c = i - r;
//                // 第一次for遍历
//                // c = 0 - 0;
//
//                // 第三次for遍历
//                // c = 2 - 2;
//
//                // 第五次for遍历
//                // c = 4 - 2;
//
//                // 奇数次遍历行数自减1，列数自加1
//                // 限定列下标c自增到总列数col(不超出界限)且行下标r自减到0(不为负数)
//                while(c < col && r >= 0){
//                // 第一次for遍历下的第一次while循环
//                // while(0 < 3 && 0 >= 0)
//
//                // 第三次for遍历下的第一次while循环
//                // while(0 < 3 && 2 >= 0)
//                // 第三次for遍历下的第二次while循环
//                // while(1 < 3 && 1 >= 0)
//                // 第三次for遍历下的第三次while循环
//                // while(2 < 3 && 0 >= 0)
//
//                // 第五次for遍历下的第一次while循环
//                // while(2 < 3 && 2 >= 0)
//
//                    // 每次赋值结束行数-1，列数+1
//                    ans.push_back(matrix[r--][c++]);
//                    // 第一次遍历下的第一次while循环
//                    // ans.push_back(matrix[0--][0++]);  // 0
//
//                    // 第三次遍历下的第一次while循环
//                    // ans.push_back(matrix[2--][0++]);  // 7
//                    // 第三次遍历下的第二次while循环
//                    // ans.push_back(matrix[1--][1++]);  // 5
//                    // 第三次遍历下的第三次while循环
//                    // ans.push_back(matrix[0--][2++]);  // 3
//
//                    // 第五次遍历下的第一次while循环
//                    // ans.push_back(matrix[2--][2++]);  // 9
//                }
//            }
//        }
//        return ans;
//    }
//};

class Solution{
public:
    vector<int> findDiagonalOrder(vector<vector<int> > & martix){
        vector<int> vec;
        if (martix.empty()){
            return vec;
        }

        int rows = martix.size();
        int cols = martix[0].size();
        int r = 0;
        int c = 0;

        for (int i = 0; i < rows+cols-1; i++) {
            if (i % 2){
                c = (c < cols) ? i : cols-1;
                r = i - c;
                while(c >= 0 && r < rows){
                    vec.push_back(martix[r++][c--]);
                }
            } else{
                r = (r < rows) ? i : rows-1;
                c = i - r;
                while (r >= 0 && c < cols){
                    vec.push_back(martix[r--][c++]);
                }
            }
        }

        return vec;
    }
};

int main(){
    vector<vector<int> > mat = {{1,2,3},{4,5,6},{7,8,9}};

    Solution s;
    for (int i = 0;i < s.findDiagonalOrder(mat).size();i++){
        cout << s.findDiagonalOrder(mat)[i] << "\t";
    }
}